Matthew Burke

March 24, 2002

Math 434

Problem 2.3

Develop all of the processes necessary to solve the TopSpin game and write up an algorithm for solving it. Include a justification for how many of the states are reachable and, if possible, which permutations in S₂₀ they represent.

Holding the topspin game with the purple disc away from you, let the counter-clockwise most position in the purple disc be the 1 position (left most position with disc away from you). Let the position clockwise from the 1 position be the 2 position, and so on for all twenty positions. Note the 20 position is one position counter-clockwise from the 1 position.

Let g and h be elements of S₂₀.

Let g = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)

Let h = (1,4) (2,3)

Note that g is equivalent to moving all of the pieces one position in a clockwise direction, and h is equivalent to a 180-degree rotation of the purple disc. So g and h generate the TopSpin group G, and G is a subgroup of S₂₀.

Note:

g^-1 = (20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1)

h = h^-1

|g| = 20 and |h| = 2

As with the Rubik’s Cube, let [hg] = hgh^-1g^-1. Therefore [hg^-1] = hg^-1h^-1g.

[hg^-1] = (1,3,5,2,4)

So [hg^-1]² = (1,5,4,3,2)

([hg^-1]² g^-4 )⁵ = (2,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3)

Then ([hg^-1]² g^-4 )⁵ g = (1,2)

With this as an inspiration, we can permute one with anything in G.

let a = ([hg^-1]² g^-4 )⁵.

Then (1,2) = ag

We claim (1,n) = a^n-1(g²a)^n-2g for 1 < n < 20

Note that a² = (20,18,16,14,12,10,8,6,4,2,19,17,15,13,11,9,7,5,3), i.e. a² fixes 1 and shifts everything else two positions counter-clockwise (except 2 and 3 which move three positions counter-clockwise in order to skip 1). Essentially we have put 1 between 3 and 4. Similarly a^n-1 will fix 1 and move everything else n-1 positions counter-clockwise putting 1 between the n and n+1.

Now in order to switch 1 and n we next need to put n between 20 and 2. Recall 1 is still in the 1 position and n is in the 20 position.

Note g²a = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19), i.e. g²a fixes the twenty position and moves everything else one position clockwise. So g²a will put n between n-2 and n-1, (g²a)² will put n between n-3 and n-2, and (g²a)^m will put n between n-(m+1) and n-m. In particular (g²a)^n-2 will put n between 1 and 2. But recall that we have already put one between n and n+1, so 20 is next to 2. Thus after a^n-1(g²a)^n-2, n is between 20 and 2 and since we moved n away, 1 is between n-1 and n+1. Finally n is in the 20 position and we want it in the 1 position, so g simply moves everything one position clockwise.

Furthermore we can permute any two distinct positions in G.

For any m, n with 1 < m < 20, 1 < n < 20, and m < n.

(m,n) = g^1-m (a^{(n - m)} (g²a)^{(n - m - 1)} g) g^m-1

Note (m,n) = (n,m) for any m and n.

Now we can show that G = S₂₀. Recall that G is a subgroup of S₂₀. Thus if we can show that S₂₀ is a subset of G we are done. Let k be an arbitrary element in S₂₀. Then k is a permutation and can be written in cycle notation. Each disjoint cycle of k may be written (n₁, n₂, … , n_i) where 1 < i < 20. The cycle (n₁, n₂, … , n_i) can be rewritten as a product of transpositions, specifically (n₁, n_i) (n₁, n_i-1) … (n₁, n₃) (n₁, n₂). Since we can permute any two distinct positions in G, we can reach k. Thus G = S₂₀; that is every permutation in S₂₀ can be reached on the TopSpin game.

An algorithm to solve the TopSpin game.

Let 1_o denote the piece with 1 written on it and 2_o denote the piece with two written on it and so on for all twenty pieces.

I. Positioning the first sixteen pieces.

1. Find 2_o and using an element of <g> move it to the 4 position (the clockwise most position in the purple disc).

i. If 1_o is not in the 1, 2, or 3 position then do hg³, and repeat i. until 1_o is in one of the 1, 2, or 3 positions.

ii. If 1_o is in one of the 1, 2, or 3 position:

a. If 1_o is in the 1 position do (g^-2h) (gh) to position 2_o next to 1_o.

b. If 1_o is in the 2 position do (g^-2h) (g^-1h) (gh) to position 2_o next to 1_o.

c. If 1_o is in the 3 position then 2_o is next to 1_o, so continue to B.

2. Repeat A replacing 2_o for 1_o and 3_o for 2_o. Continue repeating A in this manner, positioning the next highest piece, until 16_o is properly positioned next to 15_o.

II. Positioning the remaining four pieces (recall a = ([hg^-1]² g^-4 )⁵ ).

1. Using an element of <g> (probably g^-1) place 16_o in the 20 position.

i. If 17_o is in the 1 position proceed to B.

ii. If 17_o is in the 2 position do ag to position 17_o next to 16_o.

iii. If 17_o is in the 3 position do g^-1ag²ag to position 17_o next to 16_o.

iv. If 17_o is in the 4 position do h to position 17_o next to 16_o.

2. Using an element of <g> (probably g^-1) place 17_o in the 20 position.

i. If 18_o is in the 1 position proceed to C.

ii. If 18_o is in the 2 position do ag to position 18_o next to 17_o.

iii. If 18_o is in the 3 position do g^-1ag²ag to position 18_o next to 17_o.

3. Using an element of <g> (probably g^-1) place 18_o in the 20 position.

i. If 19_o is in the 1 position then do g―^-2 to finish.

ii. If 19_o is in the 2 position do ag^-1 to finish.